from typing import *
from math import inf


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:

        def kmp_next(s: str):
            n = len(s)
            next = [0] * n
            l = 0
            for r in range(1, n):
                while l > 0 and s[l] != s[r]:
                    l = next[l - 1]
                if s[l] == s[r]:
                    l += 1
                next[r] = l
            return next

        m = len(words)
        limit = len(target)
        dp = [[0] * m for _ in range(limit)]

        for i, word in enumerate(words):
            next = kmp_next(word)
            l = 0
            for j, v in enumerate(target):
                while l > 0 and (l == len(word) or word[l] != v):
                    l = next[l - 1]
                if word[l] == v:
                    l += 1
                dp[j][i] = l
        f = [inf] * limit
        for i in range(limit):
            for j in range(m):
                k = i - dp[i][j]
                f[i] = min(f[i], f[k] + 1 if k > -1 else 1)
        return f[limit - 1] if f[limit - 1] < inf else -1


s = Solution()
print(s.minValidStrings(["ccc", "a", "cbcaaaccca"], "ccbccccaaa"))
print(s.minValidStrings(["abc", "aaaaa", "bcdef"], "aabcdabc"))
